#ifndef KNAPSACK_H
#define KNAPSACK_H

#include <queue>

#include "common.h"
#include "misc.h"

class knapsack
{
private:
    int total;      /* the number of the objects */
    int capacity;   /* the knapsack capacity */

    int *weights;   /* the weights of the objects */
    int *profits;   /* the profits of each object */

    int *solution;  /* the optimal selection of weights */
    int optimum;    /* the optimum of profit */

public:
    knapsack(const int &, const int &, const int *, const int *);
    ~knapsack();

    void dp();
    void dfs();
    void bfs();

    int *get_solution();
    int get_optimum();

private:
    void dfs(node &);
};

#endif